package com.lsa.letcode.the151.reverseWordsInStr;

public class Solution {
	public String reverseWords(String str) {
		return doReverseWords(str);
	}
	
    static String doReverseWords(String str) {
    	StringBuilder s = new StringBuilder(str);
    	
        int start = -1;
        int stop = -1;
        boolean inWord = false;
        
        for (int i = 0; i < s.length(); i++) {
        	char c = s.charAt(i);
        	if (!Character.isWhitespace(c)) {
        		if (inWord) {
        			stop++;
        		}
        		else {
        			start = i;
        			stop = i;
        			inWord = true;
        		}
        	}
        	else {
        		if (inWord){
        			inWord = false;
        			reverse(s, start, stop);
        		}
        	}
		}
        if (inWord){
			reverse(s, start, stop);
		}
        reverse(s, 0, s.length() - 1);
        return normalize(s);
    }
    
    static String normalize(String s){
    	return normalize(new StringBuilder(s)); 
    }
    
    static String normalize(StringBuilder s){
    	int to = 0;
    	boolean inWord = false;
    	for (int i = 0; i < s.length(); i++) {
    		char c = s.charAt(i);
    		if (!Character.isWhitespace(c)) {
        		inWord = true;
        		s.setCharAt(to++, c);
        	}
        	else {
        		if (inWord){
        			s.setCharAt(to++, ' ');
        			inWord = false;
        		}
        	}
		}
    	if (to > 0 && Character.isWhitespace(s.charAt(to - 1))) {
    		to--;
    	}
    	return s.substring(0, to); 
    }
    
    static StringBuilder reverse(StringBuilder s, int from, int to) {
    	int len = to - from + 1;
		for (int i = from; i < from + (len >> 1); i++) {
			int j = to - (i - from);
			char c = s.charAt(i);
			s.setCharAt(i, s.charAt(j));
			s.setCharAt(j, c);
		}
		return s;
    }
}